package com.future;

import java.util.ArrayList;
import java.util.List;

/**
 * Description: 1104. 二叉树寻路
 *
 * @author weiruibai.vendor
 * Date: 2023/1/6 10:56
 */
public class Solution_1104 {

    private static Solution_1104 instance = new Solution_1104();

    public static void main(String[] args) {
        int label = 1;
        System.out.println(instance.pathInZigZagTree(label));
    }

    /**
     * 看图片 Solution_1104.png
     * 自己演练
     * 第0层 最小值和个数都是2^0 顺序左往右
     * 第1层 最小值和个数都是2^1 顺序右往左
     * 第2层 最小值和个数都是2^2 顺序左往右
     *
     * @param label
     * @return
     */
    public List<Integer> pathInZigZagTree(int label) {
        List<Integer> ans = new ArrayList<>();
        if (label < 2) {
            ans.add(1);
            return ans;
        }

        int power = 0;
        int tmp = label;
        while (tmp > 1) {
            tmp = tmp / 2;
            power++;
        }
        /**
         * 是否从左往右到小到大排序
         */
        boolean isOrder = power % 2 == 0;
        int curIndex;
        if (!isOrder) {
            curIndex = ((int) Math.pow(2, power + 1) - 1) - label; // 倒序时对应下标值
        } else {
            curIndex = label - (int) Math.pow(2, power);// 正序时对应下标值
        }
        ans.add(0, label);
        int val;
        power--;
        curIndex /= 2;
        while (power > 0) {
            isOrder = !isOrder;
            if (!isOrder) {
                /**
                 * 倒序时，第一个值就是Math.pow(2, power + 1)，但是下标从0开始，所以-1
                 * 因为curIndex是正序正序从0～curIndex
                 * eg: 15 14 13 12 11 10 9 8
                 * 假设正序时curIndex=2（即 [8 9 10 11 12 13 14 15]的下标2，值为10）
                 * 那么在倒序情况下，变成位置变成curIndex=(8-1)-2=5 对应值为10
                 */
                val = ((int) Math.pow(2, power + 1) - 1) - curIndex;
            } else {
                /**
                 * 正序时，第一个值就是Math.pow(2, power)
                 * 那么向右移动curIndex步，步长为1，对应的值就是要 Math.pow(2, power) + curIndex
                 */
                val = (int) Math.pow(2, power) + curIndex;
            }
            /**
             * 都插到数组前面
             */
            ans.add(0, val);
            /**
             * 上一级下标值
             */
            curIndex /= 2;
            /**
             * 层级--
             */
            power--;
        }
        ans.add(0, 1);
        return ans;
    }

}
